package top.minuy.structure.linear.linked;

/**
 * @author Minuy
 * @time 12:56
 * @date 2021/8/23
 */
public class LinkedList<E> {

    // 虚拟头节点
    private Node<E> dummyHead;
    // 链表大小
    private int size = 0;

    /**
     * 创建一个链表
     */
    public LinkedList() {
        this.dummyHead = new Node<E>();
        this.size = 0;
    }

    /**
     * 在链表任意位置插入元素
     *
     * @param index 要插入的位置
     * @param e     要插入的元素
     */
    public void add(int index, E e) {
        if (index < 0 || index > this.size) {
            throw new IllegalArgumentException("Add Failed. Index is illegal.");
        }

        Node<E> prev = this.dummyHead;

        // 指向插入节点的前一个节点，这里使用虚拟节点之后改变
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

//            Node<E> newNode = new Node<E>(e);
//            newNode.next = prev.next;
//            prev.next = newNode;

        // 上面的可以用一句代替
        prev.next = new Node<E>(e, prev.next);
        this.size++;
    }

    /**
     * 在链表最前面添加元素
     *
     * @param e 要添加的元素
     */
    public void addFirst(E e) {
//        Node<E> newNode = new Node<>(e);
//        newNode.next = this.head;
//        this.head = newNode;

        // 使用虚拟节点之后统一操作
        add(0, e);
    }

    /**
     * 添加元素到链表尾部
     *
     * @param e 要插入的元素
     */
    public void addLast(E e) {
        add(this.size, e);
    }

    /**
     * 获取链表大小
     *
     * @return 大小
     */
    public int getSize() {
        return this.size;
    }

    /**
     * 获取链表中的元素
     *
     * @param index 索引
     * @return 索引处的元素
     */
    public E get(int index) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("Get Failed. Index is illegal.");
        }

        Node<E> cur = this.dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        return cur.e;
    }

    /**
     * 获取链表中第一个元素
     *
     * @return 第一个元素
     */
    public E getFirst() {
        return get(0);
    }

    /**
     * 获取链表中最后一个元素
     *
     * @return 最后一个元素
     */
    public E getLast() {
        return get(this.size - 1);
    }

    /**
     * 修改链表中的某个元素
     *
     * @param index 修改的索引
     * @param e     修改后的值
     */
    public void set(int index, E e) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        }

        Node<E> cur = this.dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        cur.e = e;
    }

    /**
     * 修改链表中第一个元素
     *
     * @param e 修改后的值
     */
    public void setFirst(E e) {
        set(0, e);
    }

    /**
     * 修改链表中最后一个元素
     *
     * @param e 修改后的值
     */
    public void setLast(E e) {
        set(this.size - 1, e);
    }

    /**
     * 查找一个元素是否存在链表中
     *
     * @param e 目标元素
     * @return 存在/否
     */
    public boolean contains(E e) {
        Node<E> cur = this.dummyHead.next;
        while (cur != null) {
            if (cur.e.equals(e)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 删除一个链表中的元素
     *
     * @param index 元素所在的位置
     * @return 被删除的元素
     */
    public E remove(int index) {
        if (index < 0 || index >= this.size) {
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
        }

        Node<E> cur = this.dummyHead;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        Node<E> delNode = cur.next;
        cur.next = delNode.next;
        delNode.next = null;

        this.size--;

        return delNode.e;
    }

    /**
     * 删除一个链表中的元素
     *
     * @param e 被删除的元素
     */
    public void remove(E e) {
        Node<E> cur = this.dummyHead;
        for (int i = 0; i < getSize(); i++) {
            cur = cur.next;
            if (cur.e.equals(e)) {
                break;
            }
        }

        Node<E> delNode = cur.next;
        cur.next = delNode.next;
        delNode.next = null;

        this.size--;
    }

    /**
     * 删除链表中的第一个元素
     *
     * @return 被删除的元素
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 删除链表中的最后一个元素
     *
     * @return 被删除的元素
     */
    public E removeLast() {
        return remove(this.size - 1);
    }

    /**
     * 判断链表是否为空
     *
     * @return 空/否
     */
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("LinkedList : size=%d\n", this.size));
        for (Node<E> cur = this.dummyHead.next; cur != null; cur = cur.next) {
            res.append(cur.e.toString());
            res.append(" -> ");
        }

        res.append("null");

        return res.toString();
    }


    /**
     * 返回大小的重载
     *
     * @return int 数组大小
     * @author Minuy
     * @date 2021/11/15 19:51
     */
    public int size(){
        return getSize();
    }

    /**
     * 默认是添加到结尾
     *
     * @param e 要添加的元素
     * @author Minuy
     * @date 2021/11/15 19:50
     */
    public void add(E e) {
        addLast(e);
    }

}
